Jump game III

Time: O(N); Space: O(N); medium

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5

Output: True

Explanation:

  • All possible ways to reach at index 3 with value 0 are:

  • index 5 -> index 4 -> index 1 -> index 3

  • index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0

Output: True

Explanation:

  • One possible way to reach at index 3 with value 0 is:

  • index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2

Output: False

Explanation:

  • There is no way to reach at index 1 with value 0.

Notes:

  • 1 <= len(arr) <= 5 * 10^4

  • 0 <= arr[i] < len(arr)

  • 0 <= start < len(arr)

Hints:

  1. Think of BFS to solve the problem.

  2. When you reach a position with a value = 0 then return true.

[1]:

import collections

class Solution1(object):
    """
    Time:  O(n)
    Space: O(n)
    """
    def canReach(self, arr, start):
        """
        :type arr: List[int]
        :type start: int
        :rtype: bool
        """
        q, lookup = collections.deque([start]), set([start])
        while q:
            i = q.popleft()
            if not arr[i]:
                return True
            for j in [i-arr[i], i+arr[i]]:
                if 0 <= j < len(arr) and j not in lookup:
                    lookup.add(j)
                    q.append(j)
        return False

[2]:

s = Solution1()
arr = [4,2,3,0,3,1,2]
start = 5
assert s.canReach(arr, start) == True
arr = [4,2,3,0,3,1,2]
start = 0
assert s.canReach(arr, start) == True
arr = [3,0,2,1,2]
start = 2
assert s.canReach(arr, start) == False